#ifndef __BASIC_TREE_H__
#define __BASIC_TREE_H__

#include <basic/misc.h>

__BEGIN_DECLS

enum
{/*{{{*/
    TREE_KEY_STRING	= 0,
    TREE_KEY_INTEGER
};/*}}}*/

/*
 * 获取真实结点
 */
#define	tree_entry(ptr,type,member)	\
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

/*
 * 指定树结点中的键值
 */
#define	tree_setkey_string(node,member,link)				\
    (node)->link.key=(void *)((node)->member)
#define	tree_setkey_integer(node,member,link)			    \
    (node)->link.key=(void *)&((node)->member)

/*
 * 树是否为空
 */
#define	tree_is_empty(tree)	\
((tree)->head==&(tree)->null_link)

/*================*/
/* 自顶向下伸展树 */
/*================*/
/* 连接件 */
struct splay_link
{/*{{{*/
    struct splay_link *left, *right;
    void *key;
};/*}}}*/

/* 树 */
struct splay_tree
{/*{{{*/
    unsigned int key_type;
    struct splay_link null_link;
    struct splay_link *head;
    int num;
};/*}}}*/

/*
 * 创建伸展树
 */
extern int	/* 0:成功 */
splay_create(
        unsigned int key_type,      /* [IN] 键值类型
                                       TREE_KEY_STRING：字符串
                                       TREE_KEY_INTEGER：整型 */
        struct splay_tree *tree     /* [OUT] 树接口 */
        );

/*
 * 伸展树插入结点
 */
extern int	/* 0:成功 */
splay_insert(
        struct splay_tree *tree,		/* [IN] 树 */
        struct splay_link *I	        /* [IN] 插入结点连接件地址 */
        );

/*
 * 伸展树删除结点
 */
extern struct splay_link *	/* 指针:成功 NULL:键值不存在 */
splay_delete(
        struct splay_tree *tree,		/* [IN] 树 */
        void *key						/* [IN] 键值指针 */
        );

/*
 * 伸展树删除结点（通过连接件）
 */
extern struct splay_link *	/* 指针:成功 NULL:键值不存在 */
splay_delete_link(
        struct splay_tree *tree,		/* [IN] 树 */
        struct splay_link *D            /* [IN] 删除结点连接件地址 */
        );

/*
 * 伸展树寻找结点
 */
extern struct splay_link *	/* 指针:成功 NULL:键值不存在 */
splay_find(
        struct splay_tree *tree,		/* [IN] 树 */
        void *key						/* [IN] 键值指针 */
        );

/*========*/
/* 红黑树 */
/*========*/
struct rb_link
{/*{{{*/
    enum { RB_RED, RB_BLACK } color;
    struct rb_link *left, *right, *parent;
    void *key;
};/*}}}*/

struct rb_tree
{/*{{{*/
    unsigned int key_type;
    struct rb_link null_link;
    struct rb_link *head;
    int num;
};/*}}}*/

/*
 * 创建红黑树
 */
extern int	/* 0:成功 */
rb_create(
        unsigned int key_type,      /* [IN] 键值类型
                                       TREE_KEY_STRING：字符串
                                       TREE_KEY_INTEGER：整型 */
        struct rb_tree *tree        /* [OUT] 树接口 */
       );

/*
 * 红黑树插入结点
 */
extern int
rb_insert(
        struct rb_tree *tree,		/* [IN] 树 */
        struct rb_link *I	        /* [IN] 插入结点连接件地址 */
        );

/*
 * 红黑树删除结点
 */
extern struct rb_link *
rb_delete(
        struct rb_tree *tree,		/* [IN] 树 */
        void *key					/* [IN] 键值指针 */
        );

/*
 * 红黑树删除结点（通过连接件）
 */
extern struct rb_link *
rb_delete_link(
        struct rb_tree *tree,		/* [IN] 树 */
        struct rb_link *D           /* [IN] 删除结点连接件地址 */
        );

/*
 * 红黑树寻找结点
 */
extern struct rb_link *
rb_find(
        struct rb_tree *tree,		/* [IN] 树 */
        void *key	    			/* [IN] 键值指针 */
        );

__END_DECLS

#endif
